package array.leetcode.medium;

/**
 * @author bruin_du
 * @description 狒狒吃香蕉
 * @date 2022/8/30 0:10
 **/
public class OfferII073_MinEatingSpeed {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        // 有可能res就是最大值，那么就不会有time <= h的情况
        // 然而left = speed + 1，当合right相等就跳出循环了，就一次都没有更新res的值
        // 但是当res是最小left时，right是会靠近等于left才会跳出循环的！！
        int res = right;
        while (left < right) {
            int speed = left + (right - left >> 1);
            int time = calcTime(piles, speed);
            if (time <= h) {
                res = speed;
                right = speed;
            } else {
                left = speed + 1;
            }
        }
        return res;
    }

    private int calcTime(int[] piles, int speed) {
        int res = 0;
        for (int pile : piles) {
            res += (pile + speed - 1) / speed;
        }
        return res;
    }

    public static void main(String[] args) {
        OfferII073_MinEatingSpeed offer = new OfferII073_MinEatingSpeed();
        System.out.println(offer.minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 100));
    }
}
